package leetcode.hot100;

public class Solution416 {

    /**
        * @param nums
        * @return
        * @desc 动态规划求等分nums数组的子数组
        * dp定义：dp[n][sum(nums)/2+1], dp[i][j]表示nums[0:i]中是否存在一组数的和为j
        * dp[i][j]=
        * if(nums[i]>j) dp[i][j]=dp[i-1][j]
        * else dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]]
    */
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if(n<2) return false;
        int sum = 0;
        for (int num:nums) {
            sum += num;
        }
        if((sum&1)==1) return false;
        sum /= 2;
        boolean[][] dp = new boolean[n][sum+1];
        //初始化dp第0行
        dp[0][0] = true;
        if(nums[0]<=sum) dp[0][nums[0]] = true;
        //开始dp
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= sum; j++) {
                if(nums[i]>j) dp[i][j]=dp[i-1][j];
                else dp[i][j] = dp[i-1][j]||dp[i-1][j-nums[i]];
            }
            if(dp[i][sum]) return true;
        }
        return false;
    }
}
